package class01;

public class Code03_Near2Power {

	// 已知n是正数
	// 返回大于等于，且最接近n的，2的某次方的值
	/**
	 * 计算大于等于n的最小2的幂次方值
	 * 这是一个经典的位运算算法，常用于HashMap等数据结构中计算容量
	 * 
	 * 算法思路：
	 * 1. 先将n减1，这样可以处理n本身已经是2的幂次方的情况
	 * 2. 通过一系列的位运算，将n的二进制表示中最高位1之后的所有位都置为1
	 * 3. 最后加1，得到大于等于原数的最小2次幂
	 * 
	 * 例如：n=12(1100)，经过处理后变成15(1111)，加1后变成16(10000)
	 * 
	 * @param n 输入的正整数
	 * @return 大于等于n的最小2的幂次方值
	 */
	public static final int tableSizeFor(int n) {
		// 先减1，处理n本身已经是2的幂次方的情况
		// 比如n=8时，如果不减1，结果会是16而不是8
		n--;
		
		// 通过右移和按位或操作，将最高位1之后的所有位都置为1
		// n >>> 1 表示无符号右移1位，然后与原数按位或
		// 这一步会将最高2位都变为1
		n |= n >>> 1;
		
		// 继续右移2位并按位或，将最高4位都变为1
		n |= n >>> 2;
		
		// 继续右移4位并按位或，将最高8位都变为1
		n |= n >>> 4;
		
		// 继续右移8位并按位或，将最高16位都变为1
		n |= n >>> 8;
		
		// 继续右移16位并按位或，确保所有位都被处理
		n |= n >>> 16;
		
		// 最后加1得到2的幂次方，如果结果小于0则返回1
		// n+1会使得形如1111的数变成10000，即2的幂次方
		return (n < 0) ? 1 : n + 1;
	}

	public static void main(String[] args) {
		int cap = 120;
		System.out.println(tableSizeFor(cap));
	}

}